package model;

import java.util.ArrayList;


public class Cromossomo {

	private Boolean[] valor;
	private int n;
	private int numeroEscalas;
	private float precoTotal;
	private float tempoViagemTotal;
	private float tempoEsperaTotal;
	private float lotacaoTotal;
	

	private double aptidao;
	private double aptidaoEmpresa;
	
	public Cromossomo(int n) {
		this.n=n;
		this.valor=new Boolean[(int)Math.pow(n, 2)];
		for(int i=0;i<valor.length;i++){
			this.valor[i]=false;
		}
	}
	
	public Boolean getValor(int i) {
		return valor[i];
	}
	
	public void setValor(int i,Boolean valor){
		this.valor[i]=valor;
	}

	private void calculaNumeroEscalas(){
		numeroEscalas=-1;
		for(int i=0;i<valor.length;i++){
			if(valor[i]==true){
				numeroEscalas++;
			}
		}
	}
	
	public int getNumeroEscalas() {
		return numeroEscalas;
	}

	private void calculaPrecoTotal(Aresta[][] aresta){
		int inicioAresta=0;
		int fimAresta=0;
		this.precoTotal=0;
		
		do{
			//procura o fim da aresta 
			for(int i=inicioAresta*n;i<(inicioAresta+1)*n;i++){
				if(valor[i]==true){
					fimAresta=i%n;
					i=n*n;
				}
			}
			this.precoTotal+=aresta[inicioAresta][fimAresta].getCusto();
			inicioAresta=fimAresta;
		}while(fimAresta!=n-1);
	}
	
	public float getPrecoTotal() {
		return precoTotal;
	}

	private void calculaTempoViagemTotal(Aresta[][] aresta){
		int inicioAresta=0;
		int fimAresta=0;
		this.tempoViagemTotal=0;
		
		do{
			//procura o fim da aresta 
			for(int i=inicioAresta*n;i<(inicioAresta+1)*n;i++){
				if(valor[i]==true){
					fimAresta=i%n;
					i=n*n;
				}
			}
			this.tempoViagemTotal+=aresta[inicioAresta][fimAresta].getTempo();
			inicioAresta=fimAresta;
		}while(fimAresta!=n-1);
	}
	
	public float getTempoViagemTotal() {
		return tempoViagemTotal;
	}
	
	private void calcularTempoEsperaTotal(Aresta[][] aresta){
		int inicioAresta=0;
		int fimAresta=0;
		this.tempoEsperaTotal=0;
		int horaPousoArestaAnterior=-1;
		
		do{
			//procura o fim da aresta 
			for(int i=inicioAresta*n;i<(inicioAresta+1)*n;i++){
				if(valor[i]==true){
					fimAresta=i%n;
					i=n*n;
				}
			}
			if(fimAresta!=n-1){
				this.tempoEsperaTotal-=aresta[inicioAresta][fimAresta].gethoraPouso();
			}
			if(inicioAresta!=0){
				this.tempoEsperaTotal+=aresta[inicioAresta][fimAresta].getHoraDecolagem();
			}
			///24h
			if(horaPousoArestaAnterior!=-1 &&
			horaPousoArestaAnterior>aresta[inicioAresta][fimAresta].getHoraDecolagem()){
				this.tempoEsperaTotal+=24*60;
			}
			horaPousoArestaAnterior=aresta[inicioAresta][fimAresta].gethoraPouso();
			////
			inicioAresta=fimAresta;
		}while(fimAresta!=n-1);
	}

	public float getTempoEsperaTotal() {
		return tempoEsperaTotal;
	}
	
	public void calcularAptidao(Aresta[][] aresta){
		
		calculaNumeroEscalas();
		calculaPrecoTotal(aresta);
		calculaTempoViagemTotal(aresta);
		calcularTempoEsperaTotal(aresta);
		
		this.aptidao=
		Constantes.ALFA*this.numeroEscalas+
		Constantes.BETA*this.precoTotal+
		Constantes.GAMA*this.tempoEsperaTotal+
		Constantes.KSI*this.tempoViagemTotal;
	}
	
	private void calculaLotacaoTotal(Aresta[][] aresta){
		int inicioAresta=0;
		int fimAresta=0;
		this.lotacaoTotal=0;
		
		do{
			//procura o fim da aresta 
			for(int i=inicioAresta*n;i<(inicioAresta+1)*n;i++){
				if(valor[i]==true){
					fimAresta=i%n;
					i=n*n;
				}
			}
			this.lotacaoTotal+=aresta[inicioAresta][fimAresta].getLotacao();
			inicioAresta=fimAresta;
		}while(fimAresta!=n-1);
	}
	
	public void calcularAptidaoEmpresa(Aresta[][] aresta){
		
		calculaLotacaoTotal(aresta);
		
		this.aptidaoEmpresa=
		Constantes.ALFA2*this.numeroEscalas+
		Constantes.BETA2*this.precoTotal+
		Constantes.GAMA2*this.lotacaoTotal+
		Constantes.KSI2*this.tempoViagemTotal;
	}

	public double GetAptidao() {
		return aptidao;
	}
	
	public void gerarCromossomoValido(){
		int atual=0;
		int proximo=0;
		int i=0;
		ArrayList<Integer> usados=new ArrayList<Integer>(0);
		
		usados.add(atual);
		while(atual!=n-1 && i<3){
			do{
				proximo=(int)(Math.random()*this.n);
			}while(usados.contains(proximo) && proximo!=n);//evitar repetidos e pegar o n que n�o existe
			usados.add(proximo);
			this.valor[atual*n+proximo]=true;
			atual=proximo;
			i++;
			/*if(i==3 && proximo==n-1){
				System.out.println();
			}*/
		}
		if(i==3 && atual!=n-1){
			this.valor[atual*n+n-1]=true;
		}
	}
	
	public int getN(){
		return this.n;
	}
	
	public static int[][] selecao(ArrayListOrdenado cromossomos){
		int numeroPares=100;
		int[][] listasSelecionados=new int[2][numeroPares];
		float aptidaoTotal=0;
		double temp1,temp2;
		double temp3;
		/*int[] estatistica=new int[cromossomos.size()];
		int maior=-1;
		double maiorAptidao=0;*/
		
		for(int i=0;i<cromossomos.size();i++){
			temp3=cromossomos.get(i).GetAptidao();
			if(temp3<0){
				temp3=-1*temp3;
			}
			/*if(1/temp3>maiorAptidao){
				maior=i;
				maiorAptidao=1/temp3;
			}*/
			aptidaoTotal+=1/temp3;
		}
		
		for(int i=0;i<numeroPares;i++){
			temp1=Math.random()*(aptidaoTotal);
			temp2=0;
			for(int j=0;j<cromossomos.size();j++){
				temp3=cromossomos.get(j).GetAptidao();
				if(temp3<0){
					temp3=-1*temp3;
				}
				if(temp2+1/temp3<temp1){
					temp2+=1/temp3;
				}else{
					listasSelecionados[0][i]=j;
					//estatistica[j]++;
					break;
				}
			}
			temp1=Math.random()*(aptidaoTotal);
			temp2=0;
			for(int j=0;j<cromossomos.size();j++){
				temp3=cromossomos.get(j).GetAptidao();
				if(temp3<0){
					temp3=-1*temp3;
				}
				if(temp2+1/temp3<temp1){
					temp2+=1/temp3;
				}else{
					listasSelecionados[1][i]=j;
					//estatistica[j]++;
					break;
				}
			}
		}
		
		return listasSelecionados;
	}
	
	public static ArrayListOrdenado crossover(ArrayListOrdenado cromossomos,int[][]listasParesSelecionados,Aresta[][] aresta){
		ArrayList<Integer> verticesCrossover;
		int somatorio0=0,somatorio1=0;
		Cromossomo mae,pai;
		int n=(int)Math.sqrt(cromossomos.get(0).valor.length);
		ArrayListOrdenado filhos=new ArrayListOrdenado(0);
		ArrayList<Integer> usados;
		
		for(int k=0;k<listasParesSelecionados[0].length;k++){
			verticesCrossover=new ArrayList<Integer>(0);
			mae=cromossomos.get(listasParesSelecionados[0][k]);
			pai=cromossomos.get(listasParesSelecionados[1][k]);
			//determinar conjunto de vertices de crossover
			for(int i=0;i<n;i++){
				somatorio0=0;
				somatorio1=0;
				for(int j=0;j<Math.sqrt(cromossomos.get(0).valor.length);j++){
					if(mae.getValor(i*n+j)==true){
						somatorio0+=1;
					}
					if(pai.getValor(i*n+j)==true){
						somatorio1+=1;
					}
				}
				if(somatorio0==1 && somatorio1==1 && i!=0 && i!=n-1){
					verticesCrossover.add(i);
				}
			}
			if(verticesCrossover.size()==0){
				Cromossomo filho;
				if(mae.GetAptidao()>pai.GetAptidao()){
					filho=Cromossomo.copia(aresta, mae);
				}else{
					filho=Cromossomo.copia(aresta, pai);
				}
				filhos.add(filho);
			}
			if(verticesCrossover.size()==1){
				Cromossomo filho1,filho2;
				usados=new ArrayList<Integer>(0);
				usados.add(0);
				filho1=new Cromossomo(mae.getN());
				filho2=new Cromossomo(mae.getN());
				int grupoAtual=0;
				boolean qualGenitor=true;
				
				//filho1
				while(grupoAtual!=n-1){
					if(qualGenitor){
						for(int i=0;i<n;i++){
							if(mae.getValor(grupoAtual*n+i)){
								if(!usados.contains(i)){
									usados.add(i);
									filho1.setValor(grupoAtual*n+i, true);
									grupoAtual=i;
									break;
								}else{
									for(int j=0;j<n;j++){
										if(mae.getValor(i*n+j) && !usados.contains(j)){
											usados.add(j);
											filho1.setValor(grupoAtual*n+j, true);
											grupoAtual=j;
											break;
										}
									}
									break;
								}
							}
						}
					}else{
						for(int i=0;i<n;i++){
							if(pai.getValor(grupoAtual*n+i)){
								if(!usados.contains(i)){
									usados.add(i);
									filho1.setValor(grupoAtual*n+i, true);
									grupoAtual=i;
									break;
								}else{
									for(int j=0;j<n;j++){
										if(pai.getValor(i*n+j) && !usados.contains(j)){
											usados.add(j);
											filho1.setValor(grupoAtual*n+j, true);
											grupoAtual=j;
											break;
										}
									}
									break;
								}
							}
						}
					}
					if(verticesCrossover.contains(grupoAtual)){
						if(qualGenitor){
							qualGenitor=false;
						}else{
							qualGenitor=true;
						}
					}
				}
				//filho2
				grupoAtual=0;
				usados=new ArrayList<Integer>(0);
				usados.add(0);
				while(grupoAtual!=n-1){
					if(qualGenitor){
						for(int i=0;i<n;i++){
							if(mae.getValor(grupoAtual*n+i)){
								if(!usados.contains(i)){
									usados.add(i);
									filho2.setValor(grupoAtual*n+i, true);
									grupoAtual=i;
									break;
								}else{
									for(int j=0;j<n;j++){
										if(mae.getValor(i*n+j) && !usados.contains(j)){
											usados.add(j);
											filho2.setValor(grupoAtual*n+j, true);
											grupoAtual=j;
											break;
										}
									}
									break;
								}
							}
						}
					}else{
						for(int i=0;i<n;i++){
							if(pai.getValor(grupoAtual*n+i)){
								if(!usados.contains(i)){
									usados.add(i);
									filho2.setValor(grupoAtual*n+i, true);
									grupoAtual=i;
									break;
								}else{
									for(int j=0;j<n;j++){
										if(pai.getValor(i*n+j) && !usados.contains(j)){
											usados.add(j);
											filho2.setValor(grupoAtual*n+j, true);
											grupoAtual=j;
											break;
										}
									}
									break;
								}
							}
						}
					}
					if(verticesCrossover.contains(grupoAtual)){
						if(qualGenitor){
							qualGenitor=false;
						}else{
							qualGenitor=true;
						}
					}
				}
				//filho1.validarCromossomo(aresta);
				filho1.calcularAptidao(aresta);
				filhos.add(filho1);
				//filho2.validarCromossomo(aresta);
				filho2.calcularAptidao(aresta);
				filhos.add(filho2);
			}else if(verticesCrossover.size()==2){
				Cromossomo filho1,filho2;
				filho1=new Cromossomo(mae.getN());
				filho2=new Cromossomo(mae.getN());
				int grupoAtual=0;
				boolean qualGenitor=true;
				
				usados=new ArrayList<Integer>(0);
				usados.add(0);
				//filho1 crossover duplo
				while(grupoAtual!=n-1){
					if(qualGenitor){
						for(int i=0;i<n;i++){
							if(mae.getValor(grupoAtual*n+i)){
								if(!usados.contains(i)){
									usados.add(i);
									filho1.setValor(grupoAtual*n+i, true);
									grupoAtual=i;
									break;
								}else{
									for(int j=0;j<n;j++){
										if(mae.getValor(i*n+j) && !usados.contains(j)){
											usados.add(j);
											filho1.setValor(grupoAtual*n+j, true);
											grupoAtual=j;
											break;
										}
									}
									break;
								}
							}
						}
					}else{
						for(int i=0;i<n;i++){
							if(pai.getValor(grupoAtual*n+i)){
								if(!usados.contains(i)){
									usados.add(i);
									filho1.setValor(grupoAtual*n+i, true);
									grupoAtual=i;
									break;
								}else{
									for(int j=0;j<n;j++){
										if(pai.getValor(i*n+j) && !usados.contains(j)){
											usados.add(j);
											filho1.setValor(grupoAtual*n+j, true);
											grupoAtual=j;
											break;
										}
									}
									break;
								}
							}
						}
					}
					if(verticesCrossover.contains(grupoAtual)){
						if(qualGenitor){
							qualGenitor=false;
						}else{
							qualGenitor=true;
						}
					}
				}
				//filho2 crossover duplo
				grupoAtual=0;
				usados=new ArrayList<Integer>(0);
				usados.add(0);
				qualGenitor=false;
				while(grupoAtual!=n-1){
					if(qualGenitor){
						for(int i=0;i<n;i++){
							if(mae.getValor(grupoAtual*n+i)){
								if(!usados.contains(i)){
									usados.add(i);
									filho2.setValor(grupoAtual*n+i, true);
									grupoAtual=i;
									break;
								}else{
									for(int j=0;j<n;j++){
										if(mae.getValor(i*n+j) && !usados.contains(j)){
											usados.add(j);
											filho2.setValor(grupoAtual*n+j, true);
											grupoAtual=j;
											break;
										}
									}
									break;
								}
							}
						}
					}else{
						for(int i=0;i<n;i++){
							if(pai.getValor(grupoAtual*n+i)){
								if(!usados.contains(i)){
									usados.add(i);
									filho2.setValor(grupoAtual*n+i, true);
									grupoAtual=i;
									break;
								}else{
									for(int j=0;j<n;j++){
										if(pai.getValor(i*n+j) && !usados.contains(j)){
											usados.add(j);
											filho2.setValor(grupoAtual*n+j, true);
											grupoAtual=j;
											break;
										}
									}
									break;
								}
							}
						}
					}
					if(verticesCrossover.contains(grupoAtual)){
						if(qualGenitor){
							qualGenitor=false;
						}else{
							qualGenitor=true;
						}
					}
				}
				//filho1.validarCromossomo(aresta);
				filho1.calcularAptidao(aresta);
				filhos.add(filho1);
				//filho2.validarCromossomo(aresta);
				filho2.calcularAptidao(aresta);
				filhos.add(filho2);
				
				// simples usando o primeiro vertice de crossover
				
				filho1=new Cromossomo(mae.getN());
				filho2=new Cromossomo(mae.getN());
				grupoAtual=0;
				usados=new ArrayList<Integer>(0);
				usados.add(0);
				qualGenitor=true;
				
				//filho1 crossover simples1
				while(grupoAtual!=n-1){
					if(qualGenitor){
						for(int i=0;i<n;i++){
							if(mae.getValor(grupoAtual*n+i)){
								if(!usados.contains(i)){
									usados.add(i);
									filho1.setValor(grupoAtual*n+i, true);
									grupoAtual=i;
									break;
								}else{
									for(int j=0;j<n;j++){
										if(mae.getValor(i*n+j) && !usados.contains(j)){
											usados.add(j);
											filho1.setValor(grupoAtual*n+j, true);
											grupoAtual=j;
											break;
										}
									}
									break;
								}
							}
						}
					}else{
						for(int i=0;i<n;i++){
							if(pai.getValor(grupoAtual*n+i)){
								if(!usados.contains(i)){
									usados.add(i);
									filho1.setValor(grupoAtual*n+i, true);
									grupoAtual=i;
									break;
								}else{
									for(int j=0;j<n;j++){
										if(pai.getValor(i*n+j) && !usados.contains(j)){
											usados.add(j);
											filho1.setValor(grupoAtual*n+j, true);
											grupoAtual=j;
											break;
										}
									}
									break;
								}
							}
						}
					}
					if(verticesCrossover.subList(0, 1).contains(grupoAtual)){
						if(qualGenitor){
							qualGenitor=false;
						}else{
							qualGenitor=true;
						}
					}
				}
				//filho2 crossover simples1
				grupoAtual=0;
				usados=new ArrayList<Integer>(0);
				usados.add(0);
				qualGenitor=false;
				while(grupoAtual!=n-1){
					if(qualGenitor){
						for(int i=0;i<n;i++){
							if(mae.getValor(grupoAtual*n+i)){
								if(!usados.contains(i)){
									usados.add(i);
									filho2.setValor(grupoAtual*n+i, true);
									grupoAtual=i;
									break;
								}else{
									for(int j=0;j<n;j++){
										if(mae.getValor(i*n+j) && !usados.contains(j)){
											usados.add(j);
											filho2.setValor(grupoAtual*n+j, true);
											grupoAtual=j;
											break;
										}
									}
									break;
								}
							}
						}
					}else{
						for(int i=0;i<n;i++){
							if(pai.getValor(grupoAtual*n+i)){
								if(!usados.contains(i)){
									usados.add(i);
									filho2.setValor(grupoAtual*n+i, true);
									grupoAtual=i;
									break;
								}else{
									for(int j=0;j<n;j++){
										if(pai.getValor(i*n+j) && !usados.contains(j)){
											usados.add(j);
											filho2.setValor(grupoAtual*n+j, true);
											grupoAtual=j;
											break;
										}
									}
									break;
								}
							}
						}
					}
					if(verticesCrossover.subList(0, 1).contains(grupoAtual)){
						if(qualGenitor){
							qualGenitor=false;
						}else{
							qualGenitor=true;
						}
					}
				}
				//filho1.validarCromossomo(aresta);
				filho1.calcularAptidao(aresta);
				filhos.add(filho1);
				//filho2.validarCromossomo(aresta);
				filho2.calcularAptidao(aresta);
				filhos.add(filho2);
				
				// simples usando o segundo vertice de crossover
				
				filho1=new Cromossomo(mae.getN());
				filho2=new Cromossomo(mae.getN());
				grupoAtual=0;
				usados=new ArrayList<Integer>(0);
				usados.add(0);
				qualGenitor=true;
				
				//filho1 crossover simples2
				while(grupoAtual!=n-1){
					if(qualGenitor){
						for(int i=0;i<n;i++){
							if(mae.getValor(grupoAtual*n+i)){
								if(!usados.contains(i)){
									usados.add(i);
									filho1.setValor(grupoAtual*n+i, true);
									grupoAtual=i;
									break;
								}else{
									for(int j=0;j<n;j++){
										if(mae.getValor(i*n+j) && !usados.contains(j)){
											usados.add(j);
											filho1.setValor(grupoAtual*n+j, true);
											grupoAtual=j;
											break;
										}
									}
									break;
								}
							}
						}
					}else{
						for(int i=0;i<n;i++){
							if(pai.getValor(grupoAtual*n+i)){
								if(!usados.contains(i)){
									usados.add(i);
									filho1.setValor(grupoAtual*n+i, true);
									grupoAtual=i;
									break;
								}else{
									for(int j=0;j<n;j++){
										if(pai.getValor(i*n+j) && !usados.contains(j)){
											usados.add(j);
											filho1.setValor(grupoAtual*n+j, true);
											grupoAtual=j;
											break;
										}
									}
									break;
								}
							}
						}
					}
					if(verticesCrossover.subList(1, 2).contains(grupoAtual)){
						if(qualGenitor){
							qualGenitor=false;
						}else{
							qualGenitor=true;
						}
					}
				}
				//filho2 crossover simples2
				grupoAtual=0;
				usados=new ArrayList<Integer>(0);
				usados.add(0);
				qualGenitor=false;
				while(grupoAtual!=n-1){
					if(qualGenitor){
						for(int i=0;i<n;i++){
							if(mae.getValor(grupoAtual*n+i)){
								if(!usados.contains(i)){
									usados.add(i);
									filho2.setValor(grupoAtual*n+i, true);
									grupoAtual=i;
									break;
								}else{
									for(int j=0;j<n;j++){
										if(mae.getValor(i*n+j) && !usados.contains(j)){
											usados.add(j);
											filho2.setValor(grupoAtual*n+j, true);
											grupoAtual=j;
											break;
										}
									}
									break;
								}
							}
						}
					}else{
						for(int i=0;i<n;i++){
							if(pai.getValor(grupoAtual*n+i)){
								if(!usados.contains(i)){
									usados.add(i);
									filho2.setValor(grupoAtual*n+i, true);
									grupoAtual=i;
									break;
								}else{
									for(int j=0;j<n;j++){
										if(pai.getValor(i*n+j) && !usados.contains(j)){
											usados.add(j);
											filho2.setValor(grupoAtual*n+j, true);
											grupoAtual=j;
											break;
										}
									}
									break;
								}
							}
						}
					}
					if(verticesCrossover.subList(1, 2).contains(grupoAtual)){
						if(qualGenitor){
							qualGenitor=false;
						}else{
							qualGenitor=true;
						}
					}
				}
				//filho1.validarCromossomo(aresta);
				filho1.calcularAptidao(aresta);
				filhos.add(filho1);
				//filho2.validarCromossomo(aresta);
				filho2.calcularAptidao(aresta);
				filhos.add(filho2);
			}
		}
		return filhos;
	}
	
	public void validarCromossomo(Aresta[][] aresta){
		
		int ultimaEscala=0;
		ArrayList<Integer> usados=new ArrayList<Integer>(0);
		
		this.calculaNumeroEscalas();
		if(this.getNumeroEscalas()>3){
			int i=0;
			while(i<3){
				//encontrar a terceira escala
				for(int j=0;j<n;j++){
					if(this.getValor(ultimaEscala*n+j)){
						i++;
						usados.add(j);
						ultimaEscala=j;
						break;
					}
				}
			}
			
			//zera o cromossomo
			for(i=0;i<this.getN();i++){
				for(int j=0;j<this.getN();j++){
					this.setValor(i*this.getN()+j, false);
				}
			}
			
			//reconstrucao do cromossomo
			this.setValor(0*this.getN()+usados.get(0), true);
			this.setValor(usados.get(0)*this.getN()+usados.get(1), true);
			this.setValor(usados.get(1)*this.getN()+usados.get(2), true);
			this.setValor(usados.get(2)*this.getN()+this.getN()-1, true);
			this.calcularAptidao(aresta);
		}
	}
	
	public static void mutacao(ArrayListOrdenado cromossomo, Aresta[][] aresta){
		
		int escolhido,atual=0,anterior=-1,proximo=-1;
		int posicaoEntra,posicaoSai;
		ArrayList<Integer> usados=new ArrayList<Integer>(0);
		Cromossomo mutante=null;
		boolean mutacaoPossivel=Cromossomo.mutacaoPossivel(cromossomo);
		//evitar loop caso n�o tenha algum cromossomo com escala
		if(mutacaoPossivel){
			do{
				escolhido=(int)(Math.random()*cromossomo.size());
				//evitar q se escolha um cromossomo inexistente
				if(escolhido==cromossomo.size()+1){
					escolhido--;
				}
				mutante=cromossomo.get(escolhido);
			}while(mutante.getNumeroEscalas()==0);
			
			while(atual!=mutante.getN()-1){
				for(int j=0;j<mutante.getN();j++){
					if(mutante.getValor(atual*mutante.getN()+j)){
						usados.add(j);
						atual=j;
						break;
					}
				}
			}
			usados.remove(new Integer(mutante.getN()-1));
			int temp=(int)(Math.random()*usados.size());
			if(temp==usados.size()){
				temp--;
			}
			posicaoSai=usados.get(temp);
			do{
				temp=(int)(Math.random()*mutante.getN());
				if(temp==mutante.getN()){
					temp--;
				}
			}while(usados.contains(temp) || temp==0 || temp==mutante.getN()-1);
			posicaoEntra=temp;
			
			for(int i=0;i<mutante.getN();i++){
				if(mutante.getValor(posicaoSai*mutante.getN()+i)){
					proximo=i;
				}
				if(mutante.getValor(i*mutante.getN()+posicaoSai)){
					anterior=i;
				}
			}
			mutante.setValor(anterior*mutante.getN()+posicaoSai, false);
			mutante.setValor(anterior*mutante.getN()+posicaoEntra, true);
			mutante.setValor(posicaoSai*mutante.getN()+proximo, false);
			mutante.setValor(posicaoEntra*mutante.getN()+proximo, true);
			mutante.calcularAptidao(aresta);
		}	
	}
	
	public static ArrayListOrdenado evolucao(ArrayListOrdenado populacaoAtual,ArrayListOrdenado filhos){
		
		int tamanhoNovaPopulacao=populacaoAtual.size();
		
		for(int i=0;i<tamanhoNovaPopulacao;i++){
			filhos.add(populacaoAtual.remove(0));
		}
		filhos=filhos.sublista(0, tamanhoNovaPopulacao-1);
		return filhos;
	}
	
	public static boolean obedeceCriterioParada(ArrayListOrdenado populacao, double distanciaMedia){
		
		double media=0;
		double dentroIntervalo=0;
		double porcentagem=0.95;
		
		for(int i=0;i<populacao.size();i++){
			media+=populacao.get(i).GetAptidao();
		}
		media/=populacao.size();
		
		for(int i=0;i<populacao.size();i++){
			if(populacao.get(i).GetAptidao()<= media+distanciaMedia && populacao.get(i).GetAptidao()>= media-distanciaMedia){
				dentroIntervalo++;
			}
		}
		dentroIntervalo/=populacao.size();
		if(dentroIntervalo>=porcentagem){
			return true;
		}else{
			return false;
		}
	}
	
	public String stringComResultado(){
		
		int atual=0;
		String saida=new String();
		saida+=(atual+1)+"--";
		while(atual!=this.n-1){
			for(int i=0;i<this.n;i++){
				if(this.getValor(atual*this.n+i)==true){
					atual=i;
					saida+=i+1+"--";
				}
			}
		}
		return saida.substring(0,saida.length()-2);
	}
	
	public static Cromossomo copia(Aresta[][] aresta,Cromossomo cromossomo){
		
		Cromossomo copia=new Cromossomo(cromossomo.getN());
		for(int i=0;i<copia.getN();i++){
			for(int j=0;j<copia.getN();j++){
				copia.setValor(i*cromossomo.getN()+j, cromossomo.getValor(i*cromossomo.getN()+j));
			}
		}
		copia.calcularAptidao(aresta);
		return copia;
	}
	
	private static boolean mutacaoPossivel(ArrayListOrdenado populacao){
		boolean possivel=false;
		for(int i=0;i<populacao.size();i++){
			if(populacao.get(i).getNumeroEscalas()>0){
				possivel=true;
				break;
			}
		}
		return possivel;
	}
	
	public static Cromossomo criaCromossomo(int[] conjunto,int n,Aresta[][] grafo){
		Cromossomo cromossomo=new Cromossomo(n);
		int i;
		if(conjunto[0]==-1){
			cromossomo.setValor((n-1), true);
			cromossomo.calcularAptidao(grafo);
			cromossomo.calcularAptidaoEmpresa(grafo);
			return cromossomo;
		}else{
			for(i=0;i<conjunto.length;i++){
				if(i!=0){
					cromossomo.setValor(conjunto[i-1]*n+conjunto[i], true);
				}else{
					cromossomo.setValor(conjunto[0], true);
				}
			}
			cromossomo.setValor(conjunto[i-1]*n+(n-1), true);
			cromossomo.calcularAptidao(grafo);
			cromossomo.calcularAptidaoEmpresa(grafo);
			return cromossomo;
		}
	}
	
	public float getLotacaoTotal() {
		return lotacaoTotal;
	}

	public double getAptidaoEmpresa() {
		return aptidaoEmpresa;
	}
}
